#include <vector>
using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
//          1  -->  2  --> 3 --> 4 --> 5
// prev <-- cur   temp

class Solution
{
public:
    // 思路： 反转链表，然后比较前后两个链表是否相等
    ListNode *reverseList(ListNode *head)
    {
        ListNode *prev = nullptr; // 前一个节点
        ListNode *cur = head;     // 当前节点
        while (cur)               // 当前节点不为空
        {
            ListNode *temp = cur->next; // 保存下一个节点
            cur->next = prev;           //    反转当前节点的指针
            prev = cur;                 // 前移prev
            cur = temp;                 // 前移cur
        }
        return prev;
    }
};